/**
 * Doubly linked list
 */

#ifndef _XORG_LIST_H_
#define _XORG_LIST_H_

/**
* Returns a pointer to the container of this list element.
*
* Example:
* struct foo* f;
* f = container_of(&foo->entry, struct foo, entry);
* assert(f == foo);
*
* @param ptr Pointer to the struct list_head.
* @param type Data type of the list element.
* @param member Member name of the struct list_head field in the list element.
* @return A pointer to the data struct containing the list head.
*/
#ifndef container_of
#define container_of(ptr, type, member) \
    (type *)((char *)(ptr) - (char *) &((type *)0)->member)
#endif

/**
* The linkage struct for list nodes. This struct must be part of your
* to-be-linked struct. struct list_head is required for both the head of the
* list and for each list node.
*
* Position and name of the struct list_head field is irrelevant.
* There are no requirements that elements of a list are of the same type.
* There are no requirements for a list head, any struct list_head can be a list
* head.
*/

struct list_head {
	struct list_head *next;
	struct list_head *prev;
};
typedef struct list_head *plist_head_t ;

/*
* Simple doubly linked list implementation.
*
* Some of the internal functions ("__xxx") are useful when
* manipulating whole lists rather than single entries, as
* sometimes we already know the next/prev entries and we can
* generate better code by using them directly rather than
* using the generic single-entry routines.
*/

#define LIST_HEAD_INIT(name) { &(name), &(name) }
#define LIST_HEAD(name) \
	struct list_head name = LIST_HEAD_INIT(name)

extern void INIT_LIST_HEAD(struct list_head *list);

/**
* list_add_tail - add a newl entry
* @newl: newl entry to be added
* @head: list head to add it before
*
* Insert a newl entry before the specified head.
* This is useful for implementing queues.
*/
extern void list_add_tail(struct list_head *newl, struct list_head *head);

/**
* list_del_init - deletes entry from list and reinitialize it.
* @entry: the element to delete from the list.
*/
extern void list_del_init(struct list_head *entry);

/**
* list_empty_careful - tests whether a list is empty and not being modified
* @head: the list to test
*
* Description:
* tests whether a list is empty _and_ checks that no other CPU might be
* in the process of modifying either member (next or prev)
*
* NOTE: using list_empty_careful() without synchronization
* can only be safe if the only activity that can happen
* to the list entry is list_del_init(). Eg. it cannot be used
* if another CPU could re-list_add() it.
*/
extern int list_empty_careful(const struct list_head *head);

/**
* list_entry - get the struct for this entry
* @ptr:	the &struct list_head pointer.
* @type:	the type of the struct this is embedded in.
* @member:	the name of the list_head within the struct.
*/
#define list_entry(ptr, type, member) \
	container_of(ptr, type, member)

/**
* list_first_entry - get the first element from a list
* @ptr:	the list head to take the element from.
* @type:	the type of the struct this is embedded in.
* @member:	the name of the list_head within the struct.
*
* Note, that list is expected to be not empty.
*/
#define list_first_entry(ptr, type, member) \
	list_entry((ptr)->next, type, member)

/**
* list_for_each_safe - iterate over a list safe against removal of list entry
* @pos:	the &struct list_head to use as a loop cursor.
* @n:		another &struct list_head to use as temporary storage
* @head:	the head for your list.
*/
#define list_for_each_safe(pos, n, head) \
	for (pos = (head)->next, n = pos->next; pos != (head); \
		pos = n, n = pos->next)

#endif // _LIST_H
